from base import *
## 练习题目：
# 主要技巧：1. 分解链表； 2. 合并链表

# 1. 删除排序链表里的重复元素：(全部不留)
# me:两个指针，一个存不重复元素，一个存重复元素
# 问题是如何分辨重复元素，以及边界条件的判定
# 如何代码实现？
class Delete_Order_ListNode(object):
    def solution(self,head):
        # 构造新的链表我们适用dummy头节点：
        dummy_Duplic = ListNode(101)
        dummy_Uniqu = ListNode(101)
        Dupli = dummy_Duplic
        Uniqu = dummy_Uniqu
        p = head
        while p:
            # 特征是重复元素连在一起：
            if (p.next is not None and p.val == p.next.val) or (p.val== Dupli.val): # 这里比较难
                Dupli.next = p # 这里就会把第一次遇到的重复值存储起来，然后后面再和它对比！！ 这里比较难
                Dupli=Dupli.next
            else:
                Uniqu.next=p
                Uniqu=Uniqu.next
            p=p.next
            # 新的链表要一个一个添加元素：需要和旧表的链接断开
            Uniqu.next=None
            Dupli.next=None
        return dummy_Uniqu.next
    def test(self):
        head = list_2_ListNode([1,2,2,2,3,3,4,5,6,7,7,8])
        res = self.solution(head)
        tranverse_listnode(res)

# 二、
# 2. 378 有序矩阵中第 K 小的元素
# 中等，不懂这题为什么是中等，可能别的思路难一点
# 矩阵的列和行都是升序的，内存复杂度在O(N^2)以内
# 类比合并多个有序链表: 这里和链表没什么关系了
class Find_Kmin_Matrix(object):
    def solution(self,matrix:list,k:int):
        import heapq
        # 将matrix存入一个最小堆：
        min_heap = []
        for num in matrix:
            for ele in num:
                heapq.heappush(min_heap,ele)
        # pop到第k个值就是了：
        for i in range(k):
            res = heapq.heappop(min_heap)
        return res

# 3. 373.查找和最小的 K 对数字
# 有两个列表，存储的数是按照非递减排序的，构造数对，一个来自第一个数组，一个来自第二个数组，找到和第K小的数对
# 先跳过，等学了队列再回来看

# 4. 2给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
# 请你将两个数相加，并以相同形式返回一个表示和的链表。
# 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
# 这道题的题解给的办法是边遍历两个链表一遍存储，不算难，重点是弄明白这种类似算盘似的加法
class Add_Num_ListNode(object):
    def solution(self,l1,l2):
        dummy = ListNode(-1)
        cur = dummy
        p1,p2=l1,l2
        carry = 0 # 进位数
        while p1 or p2 or carry!=0: # 两个链表都遍历完且进位也算完了才结束（因为最高位可能也要进位）! 边界条件是难点
            val=carry
            if p1:
                val+=p1.val
                p1=p1.next
            if p2:
                val+=p2.val
                p2=p2.next
            carry = val//10
            val = val%10
            newnode = ListNode(val)
            cur.next=newnode
            cur=cur.next
        return dummy.next

# 5. 上一题的基础上，如果给出的数字是正序的，如何做？
# 思路：先反转链表，再计算，再反转链表：
# 或者借用辅助栈：
class Add_Num_ListNode2(object):
    def reverse_listnode(self,head):
        # 反转链表的思路：三个指针！！
        pre = None
        cur = head
        while cur:
            temp = cur.next # 把下一个节点存一下
            cur.next = pre # 这里不存在把原来的链断开这种事情，因为链表内定义时，next属性只有一个值，会覆盖掉
            pre = cur
            cur = temp
        return pre #
    def test_reverse(self):
        head = list_2_ListNode([1,2,3,4,5,6])
        res = self.reverse_listnode(head)
        tranverse_listnode(res)
    def solution1(self,headA,headB):
        # 先用反转链表的方法来解决试试：
        head1 = self.reverse_listnode(headA)
        head2 = self.reverse_listnode(headB)
        res = Add_Num_ListNode().solution(head1,head2)
        res = self.reverse_listnode(res)
        return res
    def listnode_2_stack(self,head):
        stack = []
        while head:
            stack.append(head.val)
            head=head.next
        return stack
    def solution(self,head1,head2):
        # 用栈的方法来解决:
        # python里的栈是用列表实现的：
        stack1 = self.listnode_2_stack(head1)
        stack2 = self.listnode_2_stack(head2)
        dummy = ListNode(-1) # 结果直接构造成链表
        i=0
        carry=0
        while i < len(stack1) or i < len(stack2) or carry!=0:
            val = carry
            val += stack1[-1]+stack2[-1]
            num = val%10
            carry = val//10
            stack1.pop()
            stack2.pop()

            # 返回结果也有技巧，因为这里也是从个位开始计算的：
            # ??? 就是用dummy.next存下了现在这个要被指向的节点 ； ★ 重要技巧
            newnode = ListNode(num)
            newnode.next=dummy.next
            dummy.next=newnode

        return dummy.next

    def test(self):
        headA=list_2_ListNode([5,2,3])
        headB=list_2_ListNode([1,5,7])
        # res = self.solution1(headA,headB)
        res = self.solution(headA,headB)
        tranverse_listnode(res)

if __name__=='__main__':
    Add_Num_ListNode2().test()








